import java.util.List;

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        // 创建dp表、初始化、填表、返回值
        int n = s.length();
        boolean[] dp = new boolean[n+1];

        dp[0] = true;
        s = " " + s;

        for (int i = 1; i <= n; i++) {
            // 推导公式和 j 有关，而j是随着i而变化的
            for (int j = i; j > 0; j--) { // j不能为0
                // [0, j-1]是true，并且[j, i]也能拼接
                if (dp[j-1] && wordDict.contains(s.substring(j, i+1))) { // substring左闭右开
                    dp[i] = true;
                    break; // 只需要找到一种情况即可
                }
            }
        }

        return dp[n];
    }
}